package 数组;

import java.util.Arrays;

/**
 * @author admin
 * @version 1.0.0
 * @ClassName 两球之间的磁力.java
 * @Description TODO
 * @createTime 2020年11月01日 11:09:00
 *
 *
 * 题意求最大化最小，类似这样的求最大化最小值、最小化最大值等都可以用二分搜索解决。
 */
public class 两球之间的磁力 {
    public static void main(String[] args) {
        int[] position={1,2,3,4,7};
        int m=3;
        Arrays.sort(position);
        int n = position.length;
        int l = 1;
        int r = (position[n-1] - position[0]) / (m - 1);
        while(l < r){
            int mid = l + (r - l + 1) / 2;//mid代表当前最小磁力
            int cnt = 1;//符合相邻两个点之间的距离>=mid的个数
            int last = position[0];//选了第一个点
            for(int i = 1; i < n; i++){
                if(position[i] - last >= mid){
                    last = position[i];
                    cnt++;
                }
            }
            if(cnt >= m){
                //mid是符合的，mid也可以更大，最优解在右半区间
                l = mid;
            }else{
                r = mid - 1;
            }
        }
        System.out.println(l);
     }
}
